Three dimensional (3D) computer graphics have become an important part of business today. Almost everyone who uses computers to communicate can appreciate the benefits of using 3D visualization and simulation technologies for data modeling, which can be applied in marketing materials, educational materials, training materials, etc. However, there are some barriers to overcome before everyone, i.e., a user with a standard personal computer (PC), can enjoy these benefits.
For example, as 3D computer models grow more sophisticated, the hardware needed to display them is constantly being pushed to capacity. Typically, in order to enjoy 3D graphics with both high interactivity and realism, a user needs to use special hardware to meet the added computational loads.
To meet this challenge, the assignee of the present application has developed a unique 3D software framework and real-time volume graphics engine called NGRAIN™ (available from i3Dimensions, Inc. of British Columbia, Canada). The software framework provides the infrastructure to assemble and manage a digital world, and offers the ability to create objects in that world. The graphics engine enables dynamic update and display of 3D image attributes and is designed to operate on common PCs without requiring specialized graphics acceleration hardware.
NGRAIN™ assembles and manages 3D images based on volume graphics. Volume graphics represent 3D objects using volume elements called “voxels.” A voxel is a 3D pixel, i.e., a pixel that has a third coordinate z in addition to x and y coordinates. FIG. 1 shows an example of a 4×4×4 volume (or voxel grid) 10 containing 64 possible locations. Eight of these locations contain voxels 12a-12h at [1,2,1], [2,2,1], [3,2,1][2,2,2], [1,3,1], [2,3,1], [3,3,1], and [2,3,2], respectively, which collectively form a 3D object 14. The data structure of NGRAIN™ is based on volume graphics, and together with its image rendering techniques, are described in detail in commonly owned Patent Cooperation Treaty Applications: Serial No. PCT/CA00/01010 (Publication No. WO 02/07088A2); PCT/CA01/00997 (Publication No. WO 02/07089A2); and
PCT/CA/01/00686 (Publication No. WO 02/07097A1), which are incorporated herein by reference.
Volume graphics are commonly used in special purpose applications, such as in medical imaging based on CT or MRI scans and in engineering imaging, which require detailed visualization of internal characteristics/structure of an object. These special purpose applications, however, involve intensive processing of voxels to create or manipulate an image, which in turn may require special-purpose hardware for accelerated rendering. Further, these special purpose applications typically do not concern themselves with many polygonal techniques, such as color texture or bump mapping, since the main purpose of these applications is generally to visualize the structural/geometrical information of an object NGRAIN™, on the other hand, is a general purpose application that achieves realistic and interactive visualization of an object that takes those polygonal techniques into account and applies them to a full range of attributes (color, intensity, normal, etc.), based on volume graphics, without requiring special hardware.
Volume graphics allow for achieving the degree of realism required for high quality simulations and visualization applications because volume models can contain both surface and internal characteristics of a real object. This is contrary to surface-based graphics, such as polygonal graphics which utilize a plurality of flat surfaces called “polygons”, typically triangles, to represent the surfaces of an 3D object. FIG. 2A hows an example of a polygon mesh object 16, which is formed of a plurality of triangle polygons 18 , (8 polygons are visible in FIG. 2A.) Each polygon is defined by its vertices 20 in the 3D Cartesian (xyz) coordinate system. Specifically, referring to FIG. 2B, each polygon is defined by its vertices 20, and each vertex 20 is typically associated with a set of attribute values such as a normal 21a, a color value 21b, and intensity 21c. A normal is a unit vector that is perpendicular to a surface at a designated point, and is used during image rendering to apply appropriate lighting to an object being rendered. A color value, or “rgb” (red, green, blue) value, is an 8-bit value from which the range of colors that can be displayed by a rendering system are generated. Intensity refers to the brightness or darkness of an object at a particular point. Note that the polygon mesh object 16 is hollow inside, i.e., there is no information concerning the internal structure/characteristics of the object 16, unlike in the case of volume graphics described above. Also, rendering of a high quality polygon mesh to approximate a curved surface usually consists of processing numerous polygons of various shapes and sizes, and thus is computationally intensive.
Despite these disadvantages, polygon mesh data are widely created and used today, as most 3D modeling software generate polygon mesh data These polygon mesh data in their present form, however, cannot be processed using NGRAIN™. To permit a user to enjoy the power of NGRAIN™, i.e., to achieve highly realistic and interactive simulation and visualization of 3D objects on a standard PC, the 3D objects that currently exist in polygon format need to be converted to voxels processable by NGRAIN™. Therefore, a need exists for a method and apparatus for efficiently converting polygon mesh data to voxels. Further, the method and apparatus should transfer any attribute data, such as color, intensity, and normal, from each polygon to the corresponding voxel because NGRAIN™ is a general-purpose application of volume graphics that requires these attribute data for rendering purposes.